////https://www.luogu.com.cn/problem/P1616
//
//#include<iostream>
//
//using namespace std;
//typedef long long ll;
//const int N = 1e4 + 10, T = 1e7 + 10;
//ll a[N], b[N], dp[T];
//
//int main()
//{
//	int t, m; cin >> t >> m;
//	for (int i = 1; i <= m; i++) cin >> a[i] >> b[i];
//
//	for (int i = 1; i <= m; i++)
//		for (int j = a[i]; j <= t; j++)
//			dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
//	cout << dp[t] << endl;
//	return 0;
//}